#include "undirected-graph.h"

UGraph *newUGraph() {
  UGraph *ug = (UGraph *) malloc(sizeof(UGraph));
  ug->size = 0;
  int i;
  for(i=0; i<1001; i++) {
    ug->v[i] = ug->end[i] = NULL;
  }
  return ug;
}

Edge *newEdge(int x, int y, double cost) {
  Edge *e = (Edge *) malloc(sizeof(Edge));
  e->dest = y;
  e->cost = cost;
  e->next = NULL;
  return e;
}


void addEdge(UGraph *ug, int x, int y, double cost) {
  if ( ug->end[x] == NULL ) {
    ug->used[ ug->size++ ] = x;
    Edge *e = newEdge(x, y, cost);
    ug->v[x] = e;
    ug->end[x] = e;
  } else {
    Edge *e = newEdge(x, y, cost);
    ug->end[x]->next = e;
    ug->end[x] = e;
  }
  if( ug->end[y] == NULL ) {
    ug->used[ ug->size++ ] = y;
    Edge *e = newEdge(y, x, cost);
    ug->v[y] = e;
    ug->end[y] = e;
  } else {
    Edge *e = newEdge(y, x, cost);
    ug->end[y]->next = e;
    ug->end[y] = e;
  }
}

void dijkstra(UGraph *ug, int source, double *result) {
  FibHeap *fh = newFibHeap();
  Entry *entries[1001];
  int i;
  for(i=0; i < ug->size ;i++) {
    result[ug->used[i]] = -1;
    entries[ug->used[i]] = NULL;
    if( ug->v[ug->used[i]] != NULL ) {
      entries[ug->used[i]] = enqueue(fh, ug->used[i], INF);
    }
  }
  decreaseKey(fh, entries[source], 0);
  while( !isEmpty( fh ) ) {
    Entry *curr = dequeueMin(fh);
    result[curr->elem] = curr->priority;
    Edge *arc;
    for(arc = ug->v[curr->elem]; arc != NULL; arc = arc->next) {
      if (result[arc->dest] != -1) continue;
      double pathCost = curr->priority + arc->cost;
      Entry *dest = entries[ arc->dest ];
      if( pathCost < dest->priority )
        decreaseKey(fh, dest, pathCost);

    }
  }
}

